﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StrategyAndSort
{
    /// <summary>
    /// 堆排序，这里采用大顶堆，从后往前排序
    /// </summary>
    class HeapSort :ISortStrategy
    {
        /// <summary>
        /// 实现堆排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        public  void Sort<T>(IList<T> array ,int keyNum =0) where T : IComparable
        {
            //建大顶堆
            //Count-2=(Count-1)-1
            for(int i= array.Count/ 2; i >=0; i--)
            {
                DownAdjust(array, i, array.Count);
            }
            //取出堆顶元素并调整堆
            for(int i = array.Count-1; i > 0; i--)
            {
                T temp = array[i];
                array[i] = array[0];
                array[0] = temp;
                DownAdjust(array, 0, i);
            }
        }


        /// <summary>
        /// 每次取出顶节点，所以下沉调整堆，形成大顶堆
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        /// <param name="parent"></param>
        /// <param name="length"></param>
        private  void DownAdjust<T>(IList<T> array,int parent,int length) where T : IComparable
        {
            T temp = array[parent];
            
            for (int child = 2 * parent + 1; child < length;  child = 2 * child + 1)
            {
                //如果右孩子存在且大于左孩子，将child定位到右孩子
                if (child + 1 < length &&array[child+1].CompareTo(array[child])>0) {
                    child++;
                }
                //根节点若是大于左右孩子，大顶堆已调整完成
                if (temp.CompareTo(array[child]) >= 0)
                    break;
                //因为temp最终是不会变的，所以可以直接将双亲节点换成子节点
                array[parent] = array[child];
                parent = child;
              
            }
            //经过往下调整，最终的parent肯定在底下，底下的直接换成父节点的值
            array[parent] = temp;
        }


    }
    
}
